1. Field of the Invention
This invention relates generally to generation of colors on color-reproduction devices--and more particularly to dot-on-dot sheet-medium printing systems, including color-halftone systems.
2. Prior Art
In recent years computer-driven machines have become available for producing color graphics--diagrams, abstract patterns or pictures--on a sheet medium such as paper. Such machines are generally controlled in a two-step process.
First a user sets up desired colors on a cathode-ray-tube (CRT) display; then the user directs the machine to print the selected colors onto the sheet medium. Both stages of control are found to be very problematic.
In the first stage, sometimes called "color adjustment" or "color compensation", although desired colors may be very clearly in mind, the user struggles with circuitous, seemingly irrational procedures for expressing to the color system just what those desired colors are. Attempts to operate a conventional color-compensation stage usually range from annoying to quite maddening.
After that difficult, patience-testing step has been satisfactorily completed, however, the user encounters new problems in the second stage, which is known as "color rendition" or "color halftoning". Here the colors and image spaces should be reproduced on the printed page--but both are found to be distorted, relative to those on the screen, in peculiar and incomprehensible ways,
These latter artifacts are even more troublesome in the sense that they are completely beyond control of even the most patient user. Prior skilled workers in this field have been unable to satisfactorily resolve either problem.
This section of the present document undertakes to cast the operating problems of prior systems in terms of basic principles of color. The result will be a hint that whatever adequate solution may be found must necessarily result from a resort to first principles of color theory. The hint will be borne out in later sections explaining the present invention.
a. Dimensionality of color
Color is three dimensional. This tridimensionality is first traceable physiologically to the origin of the color experience in at least three different photosensitive pigments (or pigment-filter combinations) that form the operative light-processing equipment of the retina.
Moving next to the physiology/physics boundary, arising from the operation of those three sensors there apparently results a corresponding set of three spectral weighting functions--evidently part of the human viewing apparatus though perhaps partly in the brain rather than the retina. The capability of a human observer to make color distinctions can be emulated by devices using these weighting functions, called "tristimulus" functions (International Commission on Illumination, 1931).
Proceeding on to psychophysical terms, the dimensionality of color is seen in Grassmann's First Law (1853): human optical apparatus is capable of exactly three kinds of color distinction. These can be expressed as changes in dominant wavelength, luminance and purity.
Next at the purely psychological or perceptual level, we will inevitably encounter again three variables. Quantitatively, however, not one but several competing coordinate systems or so-called "color spaces" have been introduced to describe the three-dimensional character of color perception.
The root reasons for this proliferation of divergent perceptual models are at the heart of the present invention and will be discussed at length. First, however, it should be appreciated that there is yet one more level or environment, one more space, in which the tridimensional character of color must be manifested--machine space.
It is interesting to notice that in a sense we here come full circle, because the eye is a color machine; the pigment-based system that drives it is as chemical, as electronic, and as mechanical as any artificial device. Now, however, we refer not to devices for distinguishing color but rather devices or machines for generating, producing, creating or manufacturing color.
The color space used in such color devices in fact mimics or tracks the color space of the eye, in certain important ways. The three retinal pigments evidently absorb selectively in (very broadly speaking) the blue, green and red spectral regions, and these are the spectral bands embodied in the tristimulus functions.
Evidently those spectral bands have some claim to special status as what might be called "natural" reference points for human color vision. As will be seen this fact sometimes has been a cause of confusion in design of equipment for color generation and control.
When we want to design devices that create and manipulate color experience, we aim to stimulate and control each retinal pigment independently. We would like to reach into the retina and excite just certain sensors, and we know just what tools can be used to do so: blue, green and red light respectively.
These choices are also desirable from the standpoint of cost-effectiveness. We must pay for each milliwatt of light that we use to create color sensation, or even to create any visual sensation, and we do not wish to do so with light that falls between, or outside, the peaks of spectral sensitivity in the retina.
Hence the choice of red, green and blue phosphors in video displays, and pigments of those same colors (or, for reasons to be discussed, their complements) in devices that produce color on paper and other media. The present invention does not undercut these choices of machine colorants.
At some level of machine operation it is necessary to communicate in machine language. At that level the machine needs a specification of what colorant to drive, and so the machine language is necessarily colorant language--for printing devices, pigment language. (In this document, a machine "pigment" means a physical coloring substance.)
b. Fundamental color spaces for color manipulation, and criteria for their selection
A natural concomitant of these phosphor and pigment choices has been the historical use of a three-dimensional color space in which red, green and blue are the defining dimensions R, G and B. For purposes of comparison only, FIG. 1 shows in an abstract form how such a space might be formulated.
For reasons that will shortly appear, color is seldom discussed, and almost never manipulated by people, in such a space. Again, however, for the lowest-level machine color space--analogous to the stream of ones and zeroes necessarily used at the lowest level in operation of a digital computer --the RGB-space choice is sensible.
Now it might be supposed, since R, G and B signals drive machine colorants, and RGB stimuli drive the retina, that RGB space is an ideal space in which to manage all color transactions. In support of this proposition can further be raised the fact that we not only work with RGB in operating our eyes but we also recognize those same colors.
That is, we consciously perceive them as such. Since it is the perceptual level that is of greatest concern for purposes of the present invention, the RGB space may seem perfectly qualified to serve for color manipulation and navigation.
We shall digress to discuss why this is not so. Experience shows that when humans need to navigate in color space their intuitions about the directions that will take them to a desired result are totally inadequate--if that color space is an RGB space. To begin with, that statement is true qualitatively:
Suppose we want some part of a color graphic to be "more reddish", or "less reddish" and we adjust a redness control to effectuate that judgment. If we are observant, we are often baffled to find that parts of the image now become more vividly or less vividly colored, and parts of the image become lighter or darker. Furthermore, the added or diminished redness that was desired--and, we know, physically provided --may or may not even be perceptible.
The above statement of inadequacy of our intuitions is even more strikingly true quantitatively. Suppose that the person who wants some part of a color graphic to be "more reddish" is a knowledgeable color scientist who understands thoroughly what causes the baffling events just described. That person now will realize what compound blendings of color stimulus would result if merely the redness were turned up, and will understand also what overall maneuvers must be made to drive to the desired result.
As a general matter such a person will be able to make adjustments--of R and G and B--that will move in the right direction in trispace. Even that person, however, will find it extremely difficult to gauge in advance roughly how big the adjustments should be to closely approach the desired result with just one or two sets of adjustments.
Therefore it is desirable to drive the RGB machine-language stage of a color system with some other stage in which color can be manipulated in a more intuitive way. It is in recognition of this consideration, for example, that color television sets are provided with color-adjustment controls that are not labelled "red", "green" and "blue"--but rather with words intended to carry some intuitive connotations for guiding the user more directly toward a desired result.
The stage of the system which is inserted to allow for adjustments must produce output signals that are then converted into RGB signals, by an arithmetic transformation. That manipulation or adjustment stage also may be driven by input signals received from a computer-screen control system, or from a broadcast signal, or from a video-playback device--any of which, in principle, may be in RGB.
Now we come to the question of what color space should be employed inside the adjustment or manipulation stage of the system--the so-called "color compensation" stage mentioned earlier. This space, since navigation is the only or principal reason for its existence, should be one which is navigable as intuitively as possible.
Essentially all modernly significant efforts to develop such a space--including that of the present invention--lead to some derivation from the parameter set which FIG. 2 presents in a generalized form. In this space, color is characterized by the following three components or parameters.
(a) One of these relates to what has been termed "a mode of appearance of the color"--see Judd, Color in Business, Science and Industry, Second Edition, p. 45 (Wiley 1963) --and is often called "value".
In speaking of self-luminous objects it is also called "brightness" (ranging on a scale from invisible to dazzling); in reference to other objects it is "lightness" (on a scale from black to white).
The other two perceptual variables describe the chromaticness of the perception:
(b) hue--commonly used to describe the colors around a color wheel, and
(c) chroma, which is the saturation or vividness of a color.
This basic or fundamental set of parameters is often identified as the "Munsell HVC" color model.
As is well known, this parameter set is popular primarily because--besides potentially providing a full quantitative, analytical description of the experience of color--it also corresponds to properties of color that are readily grasped intuitively and that seem to be natural or even fundamental. The parameters correspond closely in intuitive significance to the three variations identified in Grassmann's First Law.
As seen in FIG. 2, a familiar implementation of Munsell color space retains some grounding in retinally-referenced colorants R, G and B. Hue is seen as the angular element of a polar-coordinate system, on a six-unit cyclical scale from zero through five (or six superposed upon the origin angle zero), and those three color reference points are generally identified as related to the points zero, two and four on the hue scale.
In this context the RGB points are no longer dimensions or parameters but rather only numbers along a parameter scale; they are called "primary colors" or "primaries". As is known, the R, G and B on a practical scale need not be identically the color reference points that earlier were suggested as "natural". Desired colors can be constructed from colorants that only roughly approximate those "natural" spectral sites--or indeed from other colorants that provide adequate chromatic gamut.
The value or lightness scale passes perpendicularly through the vertex or central origin of the hue plane drawn in FIG. 2. That plane is positioned in the drawing to suggest that the origin of the value scale may be taken as the center of the lightness-darkness range, with numbers L (light) as greatest available positive value and D (dark) the greatest available negative value.
The vividness or chroma scale is represented by perpendicular radial or horizontal distance from the central lightness-darkness line LD. As will be seen, this seemingly straightforward representation has led to some of the greatest problems in color-control efforts heretofore.
Of course any point in this tridimensional color space can be represented with these three parameters. As a matter of chromatic reality, however, not all points in this space have distinct physical meaning.
Some constraints are imposed by theoretical availability of pure colors in the spectral sense. In adapting this color space to generation of colors by use of fixed individual primaries, further constraints are imposed by availability of actual colorants.
Accordingly the ranges of permissible points are often said to be enclosed within various forms of color "solid". One such color solid is shown--again in very generalized form--in FIG. 3. Both the external contours and internal structure of that solid are characterized and illustrated differently in different color models.
Since the present invention proceeds from a way of thinking about color space that is fundamentally different from ways employed earlier, particularly as to color machines or devices, we shall continue slightly further with our summary of portions of the conventional analysis.
FIG. 3 may be taken as representing very generally the colors available from a large choice of colorants. The solid has rounded upper and lower surfaces.
Those surfaces represent the boundary of the so-called "gamut" of those colorants--in other words, the extreme boundaries of the range of all available pigment choices, and combinations of those choices. All the colors that are within those gamut boundaries can be formed from those available choices and combinations, and are said to be within the gamut of available colors of the system.
The limiting case of pure chromatic or spectral colors defines the extreme equatorial rim, or a vertical tangent along that rim--which in any vertical-section plane is rounded.
The top and bottom apices represent the light and dark extrema available in the particular colorant system. These light and dark extrema, like other points on the surface of the solid, correspond to the light and dark extremes of available pigments--here specifically the nonchromatic pigments.
The color solid of FIG. 3 has been drawn with a section removed. The two faces 11a, 11b of the section represent the gamut of colors available, for the assumed large selection of colorants, in two different hue planes. That is, each section face 11a, 11b respectively represents only colors that are formed by making a great variety of lightness and vividness shadings of one specific hue, exclusively.
FIG. 4 is a like generalized representation of colors available from a selection of many primaries of different hues, but just one primary for each hue. The rounded surfaces are replaced by straight lines which connect the light and dark extrema, respectively, to the rim.
All these lines considered together form a pair of opposed cones. The rim now represents just one single point for each hue--corresponding to the physical primary selected for that hue.
Thus the rim is now the sharp intersection of upper and lower cones. Further, as a practical example the boundary rim line at each point in FIG. 4 is defined by a color point that has been selected as within the color solid of FIG. 3: real-world colorants usable in machines usually must be selected to accommodate machine constraints on viscosity, physical and color stability, and cost. For the same reason the apical points are chosen within the lightness range defined by the apices of FIG. 3.
FIG. 4 thus represents one major step from the relative abstraction of FIG. 3 toward practical machine systems. Implicit in FIG. 4, however, remains an assumption of an essentially infinitesimal spacing of an infinite number of primaries about the rim. The next step toward a practical system is to replace these by some small number--such as three to seven--of colorants spaced somewhat evenly about the rim.
Only colors within the boundary formed by a straight line between each primary can be formed from those colorants; hence the gamut of the system at its equator becomes a polygon. Above and below that polygonal equator, the gamut is defined by planes extending from the sides of the polygon to the top and bottom apices; such planes form a gamut solid (not illustrated) composed of two opposed polygonal pyramids.
FIG. 5 shows four fine leaves 11R, 11PB, 11PG, 11Y sectioned from a large-colorant-selection solid very generally like that of FIG. 3. Such sections are called "hue pages".
Near top and bottom on each hue leaf or page 11R, 11PB, 11PG, 11Y there is drawn a set of diagonal straight lines such as would be found from a single-colorant-per-hue color solid very generally like that of FIG. 4. Superimposed for reference is a cylinder of constant vividness.
The hue pages here are merely for representative hues, but are far more realistic than in FIGS. 3 and 4. They illustrate very clearly that the equatorial rim sweeps about neither a constant-lightness height nor along a constant-vividness radius--but rather varies strongly, as a three-dimensional contour, with hue.
Thus both blue-green 11BG and red 11R gamuts are available with maximum vividness that is positioned at midlightness values along the vertical "value" scale. Blue-green vividness is distinctly truncated, whereas available vividness for red is emphatically greater than for other colors.
Purple-blue 11PB and yellow 11Y, on the other hand, both have very generally midrange vividness extrema; the purple-blue vividness comes to a peak at a very low point along the value scale--producing available colors often described as "deep". The yellow vividness, however, peaks very high on the value scale, to offer colors sometimes called "brilliant".
From FIG. 5, and particularly by reference to only the straight lines on each hue page showing the available gamut on that page for some practical colorant of that hue, it is possible to visualize a color solid in which the straight lines in the four different hue pages are connected together by triangular planes. At the outer edge, these planes form an irregular rim, not a regular equator as previously suggested.
That rim rather is a highly irregular one that pokes radially in and out to the different vividnesses of the several colorants, while riding up and down to the corresponding different lightness values at those vividness points. The solid so described would represent the gamut of colors that could be formed by direct combination of the four practically usable primaries selected just inside the radially outermost point of each hue page in FIG. 5--under the constraint of using each of those primaries only directly as a primary.
As can be appreciated from visualizing such an irregular pyramidal solid, with four (or more typically just three) colorants, very large peripheral (i.e., vivid) regions would be cut off by the outer pyramidal edges--and so would be outside the solid. Those regions would represent colors excluded from the gamut, leaving distinctly limited treatments of vivid colors situated between the colorant primaries.
Actually the gamut is not that severely constrained, even with only three colorants. Each pair of those colorants can be blended to construct a complementary color at a generally diametrical point of the solid.
These complements can then be treated as if physically present, and the polygonal equator thus puffed out (angularly) in the regions between the primaries that are physically present. Accompanying that equatorial restoration is a corresponding expansion of the pyramidal upper and lower surfaces.
Now when color is analyzed for the purpose of systematizing its generation or manufacture--and especially in allowing users and automatic-machine designers to adjust or control the resulting colors--it has been natural to attempt to adapt these same three color dimensions to the analysis. Device users would like to be offered controls or adjustments which they understand in intuitive terms: for example, a knob labeled "brightness" or a computer-screen menu choice (for color to be printed on paper) marked "vividness".
To draw an example from an analogous (phosphor-based) field, however, it is a commonplace observation that twisting the brightness control on a television set is likely to change not only the brightness but the saturation and even the hue as well. Chroma adjustments often are equally frustrating because the desired fine retouching of color saturation is often accompanied by gross changes in brightness--or, again, hue.
This example merely serves to couch the problem in familiar terms. Analogous difficulties are seen in all kinds of paper or so-called "hardcopy" color images: we all encounter marginal color rendition everywhere in everyday life.
Behind the scenes, in many of such cases, were efforts to correct what seemed to be just a small error in, for example, hue--but which efforts almost inevitably resulted in unacceptable accompanying shifts in chroma or brightness.
Such results are a direct result of the unfavorable economics in iterative efforts to bring the finished colors into a reasonable approximation of what is desired. When iterative efforts fail (as is often the case) to converge but rather seem to circulate endlessly around the desired accurate or natural appearance, terms such as "uneconomic" hardly suffice.
Two conclusions may be drawn about the present state of the color-compensation art: (1) color adjustments, identified by parameters that are readily comprehended as intuitive, suffer from a lack of mutual independence; (2) apart from that seemingly basic property under control, color adjustments also fail to be reasonably well-behaved in perceptual color space.
Although our earlier discussion of RGB color space emphasized difficulties of independence of available adjustment parameters in RGB space, we also mentioned the problem of quantitation of adjustment. Unfortunately, prior efforts to develop a formulation for intuitive management of color have seized with excessive vigor upon this second criterion--quantitative regularity.
It is true that in discussing color as perceived, it is helpful to employ a color space that is perceptually linear--in other words, a space in which equal steps along any dimension correspond to increments of color perception that also appear substantially equal.
Adoption of that criterion as the major objective, however, has been to the considerable detriment of the more fundamental criterion, parametric independence. It is at this point, as will now be shown, that the prior art veers sharply away from satisfactory solutions to the problem of providing good adjustability.
This detour taken by the prior art is not a fault inherent in the fundamental HVC color space of FIGS. 2 through 5. Rather it arises in unfortunate choices for specific definitions of the parameters--particularly chroma C.
True independence (or in mathematical terms "orthogonality") of parameters may be unnecessary, but at least very low mutual sensitivity or crosstalk is highly desirable. Similarly, precise perceptual linearity may be unnecessary, but it is sensible to pursue at least a fair degree of consistency in response to like adjustments of chroma, for example, in different portions of a hue plane. The same is true of uniformity in response to like adjustments of brightness in the presence of various chroma numbers; and so on.
In response to this line of thinking it might be objected that a clear design goal for the most modern equipment should be to substantially eliminate the real need for adjustment, and simply drive the color devices to a color presentation that is both "correct" or "accurate" and "natural" For two reasons, the requirement for independent and well-behaved parameters in an adjacent color space cannot be so easily dismissed.
First, consumers will continue to want fine adjustments for use as a matter of taste or preference. Second, in modern apparatus intended to produce correct or natural color the same problems of parametric independence and regularity resurface before the color device reaches the consumer: here it is the apparatus designers who struggle with the same problems.
The reasons for the importance of independent parameters are the same in supposedly automatic color-control systems as in an earlier generation of systems nominally dependent upon operator adjustments. The colorants used to produce color--pen-discharged ink dots, for instance--simply do not come with inherent, independent adjustments for chroma, brightness, or hue.
None of these physical substances is an ideal Munsell color machine. Neither are the devices--e.g., pens--used to actuate the colorants.
This momentary reversion to thinking about machine space and colorant language does invoke a third conclusion: (3) the so-called perceptual primaries and variables employed for color adjustment fail to correspond well to "device primaries" and "device variables".
Here is a summary of the conclusions reached so far. Industrial color science has failed to develop a model of color space that is both parametrically independent and perceptually uniform, and even more emphatically has failed to develop a model that is also reasonably compatible with device parameters.
The prior art has not reached a main objective: an ability to take the input desired-color information into such a space. Therefore it is not generally possible for perceptually meaningful and independent adjustments, compensations and rendering decisions to be made easily and straightforwardly--in particular, without need for iteration.
The prior art has also fallen short of another main objective: an ability to move on into machine space with minimal distortion of the perceptual adjustments, compensations and decisions.
After some further introduction, two prominently used color models will shortly be described; as will be seen they fall short of all three objectives--independence, well-behaved navigation about color space, and correspondence to device parameters.
c. Operation of color-creating devices
Typical color output devices use a combination of--for example--red, green, blue, cyan, magenta, yellow and black colorants to generate color. These colorants conventionally are abbreviated R, G, B, C, M, Y and K respectively; or in a usual condensed notation "RGBCMYK". These systems are only capable of printing these distinct colors, limited in number, at each addressable location.
In this document these distinct colors will be called the system colorants. They include device primaries (i.e., chromatic colors RGBCMY that have hue) plus black K.
Typically the system colorants also include white ("W") --commonly for example the white of a sheet medium such as paper. In some cases white is instead constructed by blending chromatic colors--but when such blends are used in trying to produce white on an already-white sheet of paper or the like, the result is to waste pigment. Analogously, overprinting two or more pigments to approximate gray always wastes pigment and also usually produces a poor gray (i.e., one that is impure, in the sense that it includes a chromatic component).
Usually the number of actual system colorants--that is, those represented on a one-to-one basis by physical pigment substances--is small. In particular, instead of all eight colorants listed above, as mentioned in the preceding section it is common to form or construct some (e.g., red, green and blue, RGB) as combinations of others (the complements cyan, magenta and yellow, CMY).
Nevertheless these constructed (as distinguished from actual) colorants RGB usually are treated as device primaries available in their combinable form. This latter part (combinability) of the assumption results in very helpful analytical simplifications to the process of producing other colors generally--i.e., other than the full set of assumed system colorants RGB-CMY-KW.
In particular, in a system that has the six chromatic colorants CMY-RGB, plus black and white, it can be shown that in order to generate any color (within the saturation envelope of these colorants) using the device, it is necessary to apply only two colorants plus black and white. As will shortly be seen this technique for operating a CMYK device is important and valuable--but for a reasonably complete hue/saturation gamut does rest upon the assumption that the constructed colorants RGB do stand in some reasonable semblance of complementarity to the actual colorants CMY.
In order to create colors other than the actual system colorants CMYK, as is well known, the latter are positioned on the medium (e.g., white) in close adjacence. The viewer integrates perceptually the spectral bands physically emanating from the actual colorants.
The viewer thus perceives some color not present as a single pigment, and perhaps perceives a desired color or something near it. Of course, close inspection as under a magnifier reveals that that desired blend is not represented as an individual colorant.
An important special case of this is halftoning, in which dots of different colorants are distributed over some area or region of the medium. Various degrees of freedom are available in such systems, depending upon the type of color device in use: dot size, for example, can be made variable.
In printing machines driven directly by digital computers, generally more straightforward and rapid operation results from controlling only presence or absence of dots, but the dots and their spacing can be made quite small to yield reasonable overall resolution. With such machines, often halftone technique is called "digital halftoning" and the dots are called "pixels"--from the familiar convention of video display.
Many digital halftoning methods are extensions of the gray-scale halftoning case, in which gray information is generated by combinations of black and white pixels. These methods, when extended to the color case, typically assume that the colorants obey a subtractive color law.
It is for this reason that--as mentioned above--all six chromatic device primaries RGB-CMY are treated as available in combinable form even though actually only three CMY (as well as nonchromatic K) are physically present. When the printer or other device fails to obey the subtractive color law, however, color errors result because it generates device primaries R'G'B' which are treated as if they were complements RGB to the actual pigments CMY, but are not those complements.
A better way to control the resulting color is to treat such a CMYK device as having six chromatic device primaries, and to construct three R'G'B' of those as crosscombinations of the three actually present, as before--but to drop the assumption that the constructed ones R'G'B' or pseudoRGB are accurately complementary red, green and blue RGB. This releases the need to depend on the subtractive color law, for establishment of primaries.
Color combinations now can be calculated using actual properties of the constructed primaries and indeed of all the primaries. Such a system--with six known chromatic colorants corresponding at least roughly to CMY and pseudoRGB or R'G'B' plus black and white--retains the capability to generate any color (within the available saturation envelope) using only two of the colorants CMY-R'G'B' plus black and white, taking into account the known departures of R'G'B' from the complements RGB.
This capability in turn enables generation of any such color using just the four actual pigments CMYK and the white background. In the remainder of this document we shall drop the notation R'G'B' and substitute the simpler RGB, with the understanding that typically one or more of these is a constructed primary.
Some known machines, particularly some using CMYK devices, are controlled by isolating black information K for separate processing in the color-compensation stage. Those systems then retain the separate black information channel in the halftoning or rendition-driving stage.
d. The HSV color space
FIG. 6 illustrates, for one traditional color model known as "HSV" the way in which perceptual variables H, S and V are found from a given definition of a desired color rendition. Those perceptual variables are then used to control device variables (not shown).
Discussion of the HSV system is appropriate because that system could be used to control a computer-driven CRT monitor in preparing a color graphic--which can then be printed on paper by a device also driven by the same computer.
The HSV color model corresponds to a color solid that is modified from those of FIGS. 3 through 5--which correspond more closely to the classical Munsell HVC model. In HSV the color solid is just a single pyramidal cone, rather than two opposed cones.
HSV is intended to model closely the intuitive concepts of tint, shade and tone used by an artist working manually in paints. While it may accomplish this, it departs considerably from relationships in classical HVC; the departures will be discussed in detail in the following paragraphs.
In the FIG. 6 diagram, the full available colorant range or full-scale color range is identified as the constant Full at the top of the graph. The heights of the three bars marked "R.sub.in ", "G.sub.in " and "B.sub.in " represent respectively an example of the amounts or sizes of red, green and blue input information --that is to say, an exemplary color that is defined as "desired".
Of course in any given real situation any one of the three inputs could be the largest, any could be the smallest, and any could be the intermediate or middle color quantity--so the identifications of the three bars as R.sub.in, G.sub.in and B.sub.in also are only an example. The relative heights of these three bars also are only an example.
Generalized quantities--that is, the desired red, green and blue amounts in the general case--will here be denoted by the same notations in italic type R.sub.in, G.sub.in and B.sub.in
In any situation, however, there must in fact be some largest, some smallest and some middle color amount: to facilitate general treatment, therefore, the three bars are labelled "Max", "Mid" and "Min" respectively. These same notations in italics--Max, Mid and Min--will be used to designate the relative bar heights in general, which is to say the three color quantities without regard to which is blue, red or green.
For simplicity we define or normalize Full.ident.1, so that all the numbers R.sub.in, G.sub.in, B.sub.in, Max, Mid and Min are fractions. In typical machine operations Full is assigned some conventional numeric value such as 255, chosen for adequate dynamic range, and the other values are all counts too. Relative representation of all the numbers in this document as integers rather than fractions is to be considered equivalent to the fractional notation.
(These same understandings apply to FIGS. 9 and 11 too.)
Now we turn to the matter of conversion from RGB color space into HSV space.
In the HSV model as in other generally used polar models it is common to start by determining which of the RGB primaries is the largest, smallest and middle quantity, respectively, and assign values for Max, Mid and Min. Next, conversions from the input information to perceptual variables include three determinations.
One of these is a direct measurement of the variable "value" or V. This variable is set equal to the largest input number, V.ident.Max.
A second computation is addressed to "saturation" or S. It is set equal to the difference between Max and Min, but normalized by dividing into that difference the value Max: S.ident.(Max-Min)/Max, or 1-Min/Max.
A third computation determines the hue, according to a somewhat complicated formula: H.ident.C+F.sub.h, where
C=0 if R.sub.in .gtoreq.G.sub.in .gtoreq.B.sub.in PA1 C=1 if G.sub.in .gtoreq.R.sub.in .gtoreq.B.sub.in PA1 C=2 if G.sub.in .gtoreq.B.sub.in .gtoreq.R.sub.in PA1 C=3 if B.sub.in .gtoreq.G.sub.in .gtoreq.R.sub.in PA1 C=4 if B.sub.in .gtoreq.R.sub.in .gtoreq.G.sub.in PA1 C=5 if R.sub.in .gtoreq.B.sub.in .gtoreq.G.sub.in PA1 F=(Mid-Min)/(Max-Min) if C is even PA1 F=(Max-Mid)/(Max-Min) if C is odd. PA1 D.ident.decision to print pigment (computational); or "total" desired colorant quantity PA1 E.ident.error propagated from the active pixel PA1 A.ident.actual decision to print pigment PA1 P.ident.total previous error PA1 P'.ident.partial accumulation of previous error PA1 x.ident.column number of the active pixel PA1 y.ident.row number of the active pixel. PA1 hue, PA1 Fraction-Colorant, and PA1 Fraction-Black. PA1 dominant primary, PA1 subordinate primary, PA1 black, and PA1 white. PA1 the chromatic colorants, and PA1 black, and PA1 white.
This treatment--as well as the use of the hue variable--underlies all prevailing color models, including that used in the present invention.
This quantitation scheme is a specific implementation of the perceptually uniform Munsell HVC color space which we have illustrated and discussed at length, but now applying specific quantitative and conceptual definitions to the generalized Munsell concepts.
One major weakness of the HSV system is that V is set equal to the largest primary quantity present, regardless of which primary it is--and regardless of the amounts of the others that may be also present. Machine adjustments of brightness or value, conversely, are then effectuated by setting the largest primary color level equal to the user's desired overall value, or brightness, or intensity.
This is quite inadequate, because it fails to take into account either the spectral sensitivity function of the eye or the amounts of other colors that are present. Perceptually such other colors add to the apparent brightness, in complicated ways that relate to--among other things--the visual sensitivity of the eye in the corresponding different spectral regions.
One way to appreciate the problem of this misdefinition of value is to review FIG. 5. It suggests that some true or intuitive perception of lightness for saturated yellow may be in the neighborhood of 0.87, but for saturated purple-blue and red respectively may be only 0.42 and 0.38--less than half that found for yellow.
Another major inadequacy of the HSV model is the normalization of saturation S to the largest primary present Max. Conceptually a reasoned argument can be made for such a relationship, but it results in an inverse proportionality, rather than independence, between two perceptual variables S and V.
FIG. 7 shows parametric relationships on a representative hue page 111--such as any of the leaves of FIG. 5--in the HSV color model. The hue page is viewed perpendicularly.
The top diagonal line is defined as a line of unity value V. The bottom diagonal line is defined as a line of unity saturation S.
A great number of different examples could be presented to illustrate counterintuitive consequences of using such a system. Following are just three.
Suppose that a device user assigns a saturated red color to some the regions in a particular graphic and a saturated yellow to others--and then instructs the device to make all the regions equally light. The HSV-controlled device, however, will interpret this as a command to make all the regions of equal value V as defined.
It will make corresponding adjustments and report the mission accomplished. The puzzled user, however, will see clearly (and consistently with FIG. 6) that the yellow regions are twice as light as the red regions.
Next suppose that a user wishes to move 112 from a relatively light color of medium vividness to a relatively darker color of the same vividness and hue. The user is quite satisfied with the starting vividness: the color is not too gray, not to chromatic--just right in chroma--but just a little too light.
Thus the user, in effect, wishes to move vertically within a hue page such as that of FIG. 7. Curiously, however, while continuing to call for progressively lower lightness (or greater darkness) the user will find 113 that the vividness is decreasing along with the lightness.
If progress on the FIG. 7 hue page could somehow be followed, the user would be surprised to find that the HSV control system, though receiving an instruction to change value only, is pursuing a diagonal route such as the path marked in FIG. 7. Not always available, however, is even this kind of map-like assurance that the user is not being deceived by the user's own senses.
The operator simply sees that the carefully adjusted, satisfactorily vivid starting color is becoming not simply darker, as desired, but also becoming, as the user might put it, "ruined". In more analytical color-science language, the color is becoming grayer or less vivid: the combination of the two effects is a color effect often called "dirtier".
At this point the user usually concludes that the control system is one of those familiar examples of a modern device to which the user becomes a servant. The user believes that the system can be made rational if the user will only develop a mental calibration--an attunement by the user to the degree of dirtiness that can be expected in darkening a color.
To make matters worse, however, just when the user may think a collaborative person/machine control stratagem has been found, the system is likely to defeat even those newly sophisticated expectations. Here the contortion is more subtle, but thereby seems only all the harder to grasp:
If the user happens to be operating in a more-saturated region than the one in which the user performed the mental self-calibration, the system makes the rate of dirtying per unit darkening rate higher (a steeper slope for the path, if it could be seen). If the user happens to be in a less-saturated region, on the other hand, the system makes the dirtying rate with darkening lower (a shallower slope).
A third example: a user has found a color that is satisfying in all respects except that it is not quite vivid enough.
The user wishes to raise the vividness without changing the brightness. That means, in classical Munsell HVC terms, a positive radial movement: a horizontal movement 114 away from the lightness axis.
The user will find here that the color becomes not only more vivid but also darker--or, in other words, deeper. FIG. 8 shows the path 115 followed.
Deep colors can be very appealing, but that is not what this particular user wants. The user may attempt to correct by increasing 116 lightness with the "lightness" control, but in the previous example the control system will respond with increased vividness too.
The user started out to raise the vividness, but had already moved it to a desired level, so now the control system is forcing the user to overshoot the desired vividness. The user now must lower the vividness to compensate for that.
Again, if able to see the map, the user would begin to doubt the rationality of the navigation system. The user would see that outward (toward-vividness) movement obtained with the "saturation" control alone is accompanied by downward (toward-darkness) movement.
Given the user's experience with the first iteration, the user feels that thereby a degree of intuition has been achieved as to operation of the control system--but now the the user makes another disappointing discovery:
The adjustments required to obtain a desired incremental change of vividness will produce an accompanying change in lightness too--but at a different rate than before. In other words, the ratio of lightness increment to vividness increment is different, so that not only is the desired color not obtained but also the user's feeling of making progress in understanding how to use the system is defeated.
e. The HSL/HSI color model
FIGS. 8 and 9 represent another popular color-control protocol known by various acronyms such as "HSI", "HSL" and "HLS". Here the parameters are hue, saturation, and intensity or lightness--once again corresponding in a very general way to Grassmann's First Law and to the generalized three-dimensional color spaces of FIGS. 2 through 5.
The definitions of these control axes, however, differ somewhat from those in the HSV model already analyzed. This can be shown by comparing the expressions given above for converting RGB coordinates into HSL saturation S and value V with the analogous expressions for obtaining HSI/HSL saturation S and lightness L or intensity I. (To simplify matters we will use only the variable L, which is more appropriate for systems that print on paper as distinguished from self-luminous systems such as CRT displays.)
While hue is the same, the other two variables are determined from these formulae: ##EQU1## Another way to write the expressions for saturation S is: ##EQU2##
At the outset it can be appreciated that the definition of lightness as an average of two primary quantities, namely the strongest and weakest, is intended to--and does--ameliorate the unnatural selection (in the HSV system) of lightness as equal to the single strongest primary.
The dual definitions of the saturation S reflect the fact that HLS creates an opposed-cone color space, more similar in this regard to classical HVC than the HSV space. In this respect the HLS system may be seen as more advantageous.
Nevertheless the saturation S here remains inversely proportional to a lightness or darkness parameter L, 1-L (depending upon whether the color of interest is above or below the midlightness plane defined by L.ident.1/2). This inverse proportionality gives rise to interdependencies and confusions of the same sort as discussed above for HSV.
It will shortly be shown, moreover, that the interaction between this interdependency and the dual definitions of saturation S introduces a new element of operational mystification. This far surpasses the disorientations encountered in HSV space.
As noted in FIG. 9, the upper and lower straight-line borders of the HSL hue page--connecting the upper and lower apices on the value axis with the defined primary--are here treated as a single locus of constant, maximum saturation.
In other words, each point along each of these two lines, as well as the equatorial apex, represents the greatest vividness that can be obtained for the particular lightness value at that height on the outer surface of the color solid. This interpretation alone, without considering navigation within the interior of the solid, does violence to intuitive feelings about color.
To see that this is so, consider a color on the outer surface very near the upper apex of the solid--that is, along the top diagonal line, but near the top-left corner. This color in truth appears to have virtually no vividness at all; it is nearly pure gray, because its horizontal (radial) distance from the lightness axis is extremely small.
Furthermore on the gray scale it is nearly white, because its vertical distance from the "light" pole is extremely small. Nevertheless in the HVC system this exceedingly pale color lies along a constant-saturation line which passes through the pure-primary colorant point at the equatorial apex and so is is said to have the same--namely, maximum--saturation (still regarded as a measure of vividness) as that pure-primary colorant.
Also assigned the same saturation is a color on the outer surface very near the lower apex of the solid--i.e., along the bottom diagonal line, near the bottom-left corner. This color too appears to have negligible vividness: it is an extremely dusky or dirty color, nearly pure gray and nearly black, but lies along the same constant-saturation line as the extremely pale color point (and the pure-primary colorant) considered previously.
If two colors are compared that are both along the two diagonal outer lines, in general the system's navigational equipment reports a difference in lightness. It persists in the interpretation, however, that no difference in saturation (vividness?) can be detected.
Small wonder that a user relying upon such a system is confused! This, however, is not the end of the story.
When the user takes controls in hand and moves off the relatively safe boundary of the solid into the interior, the maneuvering rules are generally analogous to trying to drive across a large, open, seemingly structureless which requires indirect routes. To simply move to a plane of greater lightness, the user shifts the "lightness" control--but instead of maintaining 212 a color of intuitively or perceptually unchanged vividness (FIG. 10), the perceived vividness first bounds rightward 215 to a maximum and then--with no change in direction of operation of the "lightness" control--reverses field and dives back leftward 217, 217', toward no vividness.
An undesirable result arises also in attempting to simply raise or lower the vividness. In complying with such a command the HVC autopilot will necessarily set off on a horizontal course 213, and reasonable response to adjustment will be enjoyed when the user is operating in, say for example, the midlightness region (FIG. 11).
Response would be slow, however, near the apices, the very-light and very-dark regions--and after cranking on the control for a long while 213' the user may be dismayed to find that a lot of time has been wasted: the end of the adjustment range will have been reached without reaching any appreciable perceived vividness.
Perhaps the machine designer will notice these effects and select instead a lightness region some two-thirds of the way toward top or bottom apices, and assign the full adjustment range to the corresponding length of the constant-lightness line at that height. This will be an improvement--but still by definition of the system cannot meaningfully improve performance very near the apices.
Such a redefinition of the control scale would be a typical accommodation or so-called "engineering tradeoff", but now results in unsatisfactory operation 213 near the mid-lightness point--in the range most often used. Now the control produces relatively large horizontal (radial) steps for relatively small adjustments, trying to equalize the incremental progress at the middle of the color solid with the analogous incremental progress at top and bottom of the color solid, in terms of saturation as defined.
Unfortunately now the high effective leverage of the control knob in the midlightness range will produce relatively large changes 213 in vividness as perceived, for relatively small adjustments. The machine, in short, now oversteers in perceptual vividness, making the vividness react too abruptly to small steering corrections.
The system condenses all of the user's potentially desired range of vividness numbers into a very small part of the available range of adjustment--and wastes a large fraction of that adjustment range. (At this juncture the skilled designer may join the user in dismay: it is not only hard to control the system but hard to produce a satisfactory design.)
Such operation may be more than merely annoying if the adjustment is attached to a digital control with a relatively limited dynamic range--such as the popular numbers zero through 255. That would be a reasonable expectation, since the control system is touted as perceptually uniform and in a truly uniform system 2.sup.8 bits should suffice.
In this case the entire candidate range of perceptual vividness could be forced into a narrow numerical interval. With that much gran- ularity it would be a coincidence for the user to find an available vividness that is considered suitable.
Of course the system designer has a number of available options, such as gearing the adjustment sensitivity to lightness or providing "fine" and "coarse" adjustments, or allowing the user to set the adjustment range about a desired point. To begin with, the skilled designer in general may have little-better view of the FIG. 7, 8, 10 and 11 road maps than the user, and so may be unable to systematize the observations enough to see what the problem is.
Furthermore the designer who somehow is able to see those strange detours taking place within the color solid may not be able to perceive how to prevent them.
f. Conventional operation of color-rendition drivers
As already mentioned in section c, computer-driven color devices for printing color images on sheet media generally produce colors as blends of just a few physically present colorants--and do so by taking advantage of the observer's ability to perceptually blend physically adjacent color dots.
In a sense this technique could be said to exploit a weakness rather than an ability of the observer, who is simply unable to resolve closely adjacent fine details and instead substitutes a perception as to their composite meaning. In any event the adjacency-blend technique for constructing a color pattern, diagram, picture or other graphic is well established.
Generally a separate computational stage--sometimes even embodied in a separate apparatus--is employed to determine the assignment of different colorants to the various available dot positions in a color-halftone graphic. This colorant-to-dot-position assignment stage is sometimes called "digital halftoning" or "rendition" of the desired color.
Since this rendition driver must make decisions about actual machine colorants, naturally it operates in machine-colorant space. Commonly therefore the earlier color-compensation or adjustment stage includes at its output a conversion step in which its perceptual-space decisions are translated (often translated back) to machine language--i.e., colorant space such as RGB or CMYK--for use in the rendition.
After such a system has done its work, it is natural for a user to compare the printed results with the desired-color input on the CRT screen. Such comparison generally reveals that the rendition driver has selected, for individual dot positions, colors that do not appear at all in the on-screen definition of desired color.
It might be thought that such distortions would affect only a few isolated dots, virtually invisible in large fields of color. Even in the interiors of large fields, however, that is not reliably so. At abrupt color-field boundaries and particularly in relatively small regions of distinctive color, especially serious problems can arise.
In those contexts, conventional digital-halftoning schemes allow accumulated errors to propagate as quite visible and even conspicuous sprinklings of chromatically anomalous dots. Critical customers find such renditions unacceptable.
The system workings that produce these questionable results will now be described.
Conventional digital color halftoning has evolved from a technique developed in monochrome by Floyd and Steinberg, "An Adaptive Algorithm for Spatial Gray Scale", Intl., Symp. Dig. Tech. Papers at 36 (SID 1975). The original technique, for use in devices using only two colorants--black and white-- attempts to make statistical decisions about pixel-printing locations in such a way as to yield a smooth rendering of desired gray-scale information.
At each printer pixel location (x,y), the decision whether or not to print a black dot is made by comparing the total desired gray information D.sub.k --in terms of white W.ident.O, and black K.ident.1--to a fifty-percent threshold. The subscript "k" identifies the processing as relating to grayness or in other words a quantity of black colorant.
If the quantity of the total desired monochrome level D.sub.k is greater than that fifty-percent threshold, D.sub.k &gt;1/2, then the pixel is printed black. Otherwise it is printed white--which ordinarily, with a white medium, simply means left unprinted.
In either case, in general an error (E.sub.k) is generated which represents gray information that is not yet taken into account in terms of what actually appears on the printed medium. Subsequent pixels must account for this residual E.sub.k.
When a total desired grayness level D.sub.k is less than fifty percent, D.sub.k &lt;1/2, and a dot is therefore not printed, the error E.sub.k from that pixel position is equal to the entire amount of the unrelieved quantity D.sub.k --that is, the total desired quantity D.sub.k minus the actual quantity 0, for a deficiency of E.sub.k =D.sub.k -0=+D.sub.k. When the total desired grayness D.sub.k exceeds fifty percent D.sub.k &gt;1/2 and a dot is printed, the error from that position equals the total desired quantity D.sub.k minus the printed quantity 1, which comes to an overshoot of E.sub.k =D.sub.k -1, a negative number.
The error information E.sub.k, whether positive or negative, is weighted and accumulated in future pixel locations--typically several different nearby locations--for use when those pixel decisions are made. FIG. 12 illustrates a conventional pattern for distribution of error from an active pixel (x,y), in other words the pixel for which a print decision is being made.
As can be seen, this diffusion pattern moves various fractions of the error from the active pixel into one not-yet-reached pixel in the same row--in other words, the next pixel in line for decision--and into three pixels in the following row. Errors propagated to unused pixel positions (past the edge of the frame, for instance) simply are discarded.
More specifically, the distribution typically assigns to the adjacent pixel (x+1,y) in the same row 7/16 of the error. To the centrally adjacent pixel (x,y+1) in the following row is assigned 5/16 of the error, and to the two pixels (x-1,y+1) and (x+1,y+1) adjoining that pixel 1/16 and 3/16 of the error respectively. (Various other allocation patterns have been proposed, and some have been used, in attempts to obtain visually more satisfying results.)
Later the digital-halftoning system receives or takes up each subsequent pixel for processing of the desired grayness at its location. Before making the threshold decision for that subsequent, then-current pixel, the previously accumulated grayness error E.sub.k is added to the desired grayness K at the then-current pixel.
The sum represents the "total" desired grayness level D.sub.k used in the algorithm discussed in the second preceding paragraph. In that "then current" pixel, grayness error E.sub.k in general will have been accumulated from several different nearby prior pixels.
These same procedures are described below in terms of formulae: ##EQU3## where K.ident.desired grayness level, amount of black pigment
For reasons that will become clear, the decision and error variables D, E, A, P and P' as well as the position coordinates x and y are here defined in general terms for any pigment.
The process continues until all pixel decisions have been made. Statistically all the desired grayness information elements K then have been used to provide the best rendering of the image.
As seen in FIG. 12, the error E generated in each pixel is typically spread out over several adjacent pixels, and a contribution from that error often can be regarded as redistributed or respread from those into further adjacent pixels --and yet further ones, and so on. This behavior of the error is analogized to diffusion of a fluid; hence the term "error diffusion".
To effectuate this plan, an error-accumulation buffer or memory is established for each pixel location x,y as the progressive rendition process approaches that pixel. Errors allocated to that pixel from others previously processed are simply added into the corresponding buffer.
In color applications, the Floyd-Steinberg method is applied to each of the components or primaries of the RGB or CMYK machine space independently. That is, the pixel decisions for each device-primary color are independent.
Precisely the same formulae shown above for black are used for each of the machine colorants, except that for each chromatic primary of course the subscript "k" identifying black pigment is replaced by a suitable designation of that primary. Thus e.g., in the case of red, representative lines of the above formulae may read (F.ident.desired input fraction): ##EQU4##
For color machines that can print black K independently, an effort is made to extract black information from the RGB or CMY pixels, and isolate that information to drive the black-printing device. This objective is salutary, since color-black is in principle produced far more efficiently and accurately by black ink than by combinations of others.
In general, however, such systems are able to extract only a rather poor approximation to the desired black information, thereby introducing another source of dissatisfaction with final printed colors.
To effectuate this plan in a color regime, the procedure establishes not just one buffer but three or four--in any event, one buffer or memory location for each machine pigment in use--for each pixel being approached. Error contributions can now be separately added (taking account of their algebraic sign of course) for each primary colorant RGB or CMYK.
The procedure leads to three or four actual print decisions A.sub.r, A.sub.g and A.sub.b --or A.sub.c, A.sub.m, A.sub.y and A.sub.k as the case may be--one for each colorant. In every way the decision for each pigment proceeds independently, to either print one or more color dots (or white W--i.e., no dot) in each pixel position.
In event the system decides to print more than one colorant in a single pixel, that is exactly what occurs: the pigments mix and the resulting color is formed by the combined influences of the colorants. As suggested already, it is often assumed that they will operate in linear superposition to produce the results predicted by a subtractive color law.
As indicated at the outset, the rendition system just described allows dots of all colors to propagate in areas where the desired color is a shaded device primary--which is to say, a combination of a pure chromatic colorant with gray. As a particularly flagrant special case of such situations, the machine output frequently contains color information where the input color is only gray information.
These effects are readily seen in some flesh tones of scanned images, in gray-scale images, and most interestingly even in large solid fields of shaded color--for instance, those used as backgrounds in business graphics.
Another manifestation appears at relatively abrupt color transitions--sharp divisions between regions of distinctly different desired color. Often the colorants of one region diffuse into the other, blurring the demarcation.
Such performance results in color effects often perceived as incongruous. Lemons, for example, that are tinted with green dots, and lawns sprinkled with pixels of blue, call particular attention to the inability of the rendition system to track basic decisions laid down firmly at the earlier color-compensation stage.
It should be emphasized that a rendition driver produces such effects while functioning correctly as designed. That is to say, as long as operation of the halftoning driver is evaluated only in, say, RGB space, that operation may be found flawless: the colors just described as "anomalous" are perfectly valid representations of the RGB input colors to the driver.
Ironically the very characteristic that would be particularly prized in operation of a perceptual color space employed for color-compensation or -adjustment purposes--namely, independence of parameters--is here seen to be associated with major problems in operation of a machine space employed for color-rendition or -halftoning purposes.
g. Summary
Prior color generation systems suffer from two distinct failings--first at the compensation stage and then later at the rendition stage.
The first places difficult hurdles in the path of an operator or system designer attempting to obtain color effects that are natural or accurate--or simply preferred. The apparatus interprets perceptually straightforward instructions in counterintuitive baffling ways, which require the user to struggle through multiple iterations in setting up the target color effects (typically displayed on a CRT).
The rendition-stage failings defeat expectations of the user who has patiently surmounted those operating hurdles at the compensation stage and has succeeded in creating a satisfactory color scheme. The user then anticipates a printed output color rendition closely tracking the satisfactory scheme, but finds instead a rendition containing blurred image-element edges, bleeding colors, and perceptually irrelevant pigments even within broad fields.
The literature of the prior art in this field has failed to identify either of these problems in terms of basic color principles or otherwise. The prior art fails to find underlying relationships between the two problems, and fails to resolve either one.